package zcw.com.lib_leet_code;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created by 朱城委 on 2021/7/12.<br><br>
 *
 * 存在重复元素 II
 */
public class Topic219 {

    public static void main(String[] args) {
        Topic219 instance = new Topic219();

        int[] array = new int[] {1,2,3,1};
        System.out.println(instance.containsNearbyDuplicate(array, 3));

        array = new int[] {1,0,1,1};
        System.out.println(instance.containsNearbyDuplicate(array, 1));

        array = new int[] {1,2,3,1,2,3};
        System.out.println(instance.containsNearbyDuplicate(array, 2));
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> set = new HashSet<>();

        for(int i = 0; i < nums.length; i++) {
            if(i > k) {
                set.remove(nums[i - k - 1]);
            }

            if(!set.add(nums[i])) {
                return true;
            }
        }

        return false;
    }

    public boolean containsNearbyDuplicate2(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>();

        for(int i = 0; i < nums.length; i++) {
            Integer oldIndex = map.put(nums[i], i);
            if(oldIndex != null && i - oldIndex <= k) {
                return true;
            }

            map.put(nums[i], i);
        }

        return false;
    }
}
